\documentclass{ctexart}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{geometry}
\usepackage{framed}
\usepackage{color}
\usepackage{subfigure}
\usepackage{tikz}
\usetikzlibrary{positioning, shapes.geometric}
\definecolor{shadecolor}{rgb}{0.92,0.92,0.92}
\title{双链表List的设计和实现}


\author{梁婧 \\ 信息与计算科学，3210105193}

\begin{document}

\maketitle

\section{双链表实现思路}
由于双向链表需要能够读取到所在节点的前后两个节点的位置，故可以将List中的Node类型稍作修改，使其同时记录包含指向其前后的节点的指针。同时通过适当的构造函数逻辑，保证在进行插入或者删除时结点内部的指针指向修改合理。

同时因为迭代器存储指向“当前结点”的指针，且尾部标志是一个有效的位置。故可以通过在List两端添加额外的节点来简化特例。
\section{find函数实现思路}
find函数的代码如下

\begin{shaded}
\begin{verbatim}
 iterator find( Object & x)
  {
    int flag_find = 0;
    iterator itr = begin();
    int i=1;                                     //用于记录查找元素的显性位置
    iterator itr_end = end();
    while(itr != itr_end){
      if( *itr == x ){
	std::cout << "您查找的元素在List中第" << i << "个位置\n" <<std::endl;
	return itr;
      }
      itr++;
      i++;
    }
    std::cout << "没有在List中发现您查询的元素\n" << std::endl;
    return begin() ;
  }

\end{verbatim}
\end{shaded}
主要思路为从List的第一个元素开始遍历整个List.如果发现需要查找的元素，则提示元素已找到，并返回该元素所在的节点位置。如果便利了整个List都没有找到该元素，则提示List中没有发现该元素，并返回List的第一个结点的位置。
  



\section{main函数设计思路}
main测试函数为可重复测试函数。

在创造空白List后用户输入初始的表中的元素。之后程序给用户提供可选择的操作列表，用户可以根据需求重复操作。在操作结束后可选择是否重复测试。
\section{测试记录}
测试记录为运行test文件测试时shell的显示。

注意在自行运行test文件时，插入和删除操作中，元素的位置不可以输入整数之外的类型，否则可能会导致程序卡死。我没有找到相关的限制输入类型的语法，所以只能遗憾地吧这个bug保留下来。
\begin{shaded}
\begin{verbatim}
ceviche@ceviche:~/chengxu$ ./test 
创建空白测试用例 
请输入List中的元素(测试中默认为整数)
1
1 

是否要继续输入？如果输入，请按1.如果停止输入，请按0.
1
请在下方输入List的下一个元素
2
1 2 

是否要继续输入？如果输入，请按1.如果停止输入，请按0.
1
请在下方输入List的下一个元素
3
1 2 3 

是否要继续输入？如果输入，请按1.如果停止输入，请按0.
1
请在下方输入List的下一个元素
4
1 2 3 4 

是否要继续输入？如果输入，请按1.如果停止输入，请按0.
1
请在下方输入List的下一个元素
5
1 2 3 4 5 

是否要继续输入？如果输入，请按1.如果停止输入，请按0.
0
您输入的列表为
1 2 3 4 5 

/**<初始化List*/


在下方输入相应的序号选择想要执行的操作
可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
1
请输入想要插入的元素
11
请输入想要插入元素的位置
1
11 1 2 3 4 5 

可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
1
请输入想要插入的元素
12
请输入想要插入元素的位置
7
11 1 2 3 4 5 12 

可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
1
请输入想要插入的元素
13
请输入想要插入元素的位置
23
您输入的位置超出了数组,无法执行操作
可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
1
请输入想要插入的元素
13
请输入想要插入元素的位置
-2
输入的位置不合法，不执行操作
/**<插入功能测试*/


可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
2
请输入想要删除元素的位置
1
1 2 3 4 5 12 

可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
2
请输入想要删除元素的位置
6
1 2 3 4 5 

可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
2
请输入想要删除元素的位置
7
您输入的位置超出了数组,无法执行操作
可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
2
请输入想要删除元素的位置
-1
输入的位置不合法，不执行操作
/**<删除功能测试*/


可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
3
请输入您想要查找的元素
1
您查找的元素在List中第1个位置

可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
3
请输入您想要查找的元素
43
没有在List中发现您查询的元素
/**<查找功能测试*/


可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
4
1 2 3 4 5 
/**<输出功能测试*/

可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
12
你输入了错误的数字，请在下方重新输入
可执行操作列表
[1]插入
[2]删除
[3]查找
[4]打印
[5]结束操作
5
是否重新开始测试？
若是，请输入1.若结束程序，请输入0.
0
测试结束
ceviche@ceviche:~/chengxu$ 

\end{verbatim}
\end{shaded}


\end{document}

